%\subsection{Non-Convexity}
We start by showing that the set of equilibria for a preference game may not be convex. This gives some intuition for why it may be difficult to find an equilibrium.

\label{sec:nonconvex}
\begin{theorem}
There exists an instance of the preference game for which the set of equilibria is not convex.
\end{theorem}
%\junk{REMOVE THIS

\begin{proof}

\begin{figure}[htb]
\centerline{
\subfloat[The $a$ players assign weights $1/2,1/2$, the $b$ players both use $b_1$, the $c$ players both use $c_2$. \label{fig:convex_eq1}]{\includegraphics[width=2.5in]{convex_eq1.jpg}}
\hfil
\subfloat[The $a$ players assign weights $1/2-1/2$, the $b$ players both use $b_2$, the $c$ players both use $c_1$. \label{fig:convex_eq2}]{\includegraphics[width=2.5in]{convex_eq2.jpg}}}
\centerline{
\subfloat[Combining half of each equilibrium, $x$ will assign $1/2$ to $a_1$, $1/4$ to each of $b_1$ and $c_1$. $x$ could improve by assigning weight only to $a_1$ and $b_1$. \label{fig:convex_comb}]{\includegraphics[width=2.8in]{convex_comb.jpg}}}
\caption{Example of an instance of the preference game for which the equilibrium
set is not convex.
\label{fig:nonconvex}}
\end{figure}

\junk{
\begin{figure}[htb]
\begin{subfigure} [The $a$ players assign weights $1/2,1/2$, the $b$ players both use $b_1$, the $c$ players both use $c_2$. \label{fig:convex_eq1}] {
\includegraphics[width=2in]{convex_eq1.jpg}
}
\end{subfigure}
\begin{subfigure} [The $a$ players assign weights $1/2-1/2$, the $b$ players both use $b_2$, the $c$ players both use $c_1$. \label{fig:convex_eq2}] {
\includegraphics[width=2in]{convex_eq2.jpg}
}
\end{subfigure}
\begin{subfigure} [Combining half of each equilibrium, $x$ will assign $1/2$ to $a_1$, $1/4$ to each of $b_1$ and $c_1$. $x$ could improve by assigning weight only to $a_1$ and $b_1$. \label{fig:convex_comb}] {
\includegraphics[width=2in]{convex_comb.jpg}
}
\end{subfigure}
\caption{Example of an instance of the preference game for which the equilibrium
set is not convex.
\label{fig:nonconvex}}
\end{figure}
}

Consider the following instance of the preference game.  We have 3 sets of 2
players each, $a_1, a_2$, $b_1, b_2$, $c_1, c_2$, and one additional
player, $x$.  The preference lists for these nodes are: $a_1$: $(a_2,
a_1)$; $a_2$: $(a_1, a_2)$; $b_1$: $(b_2, b_1)$; $b_2$: $(b_1, b_2)$;
$c_1$: $(c_2, c_1)$; $c_2$: $(c_1, c_2)$; $x$: $(a_1, b_1,c_1, x)$.
(Each list gives strategies in order from most preferred to least
preferred.)  We now show two equilibria whose linear combination is
not an equilibrium.  In equilibrium $w$ (figure
\ref{fig:convex_eq1}): $w_{a_1}(a_1) = \frac{1}{2}$, $w_{a_1}(a_2)
=\frac{1}{2}$, $w_{a_2}(a_2)=\frac{1}{2}$, $w_{a_2}(a_1) =
\frac{1}{2}$, $w_{b_1}(b_1) = 1$, $w_{b_2}(b_1) = 1$, $w_{c_1}(c_2) =
1$, $w_{c_2}(c_2) = 1$, $w_x(a_1) = \frac{1}{2}$, $w_x(b_1) =
\frac{1}{2}$.  In equilibrium $w'$ (figure \ref{fig:convex_eq2}):
$w'_{a_1}(a_1) = \frac{1}{2}$, $w'_{a_1}(a_2) =\frac{1}{2}$,
$w'_{a_2}(a_2)=\frac{1}{2}$, $w'_{a_2}(a_1) = \frac{1}{2}$,
$w'_{b_1}(b_2) = 1$, $w'_{b_2}(b_2) = 1$, $w'_{c_1}(c_1) = 1$,
$w'_{c_2}(c_1) = 1$, $w'_x(a_1) = \frac{1}{2}$, $w'_x(c_1) =
\frac{1}{2}$. 
It is easy to verify that $w$ and $w'$ are both equilibria, and in a solution
$\lambda \cdot w + (1 - \lambda) \cdot w'$ (for any $\lambda >
\frac{1}{4}$) (figure \ref{fig:convex_comb} shows $\lambda=\frac{1}{2}$), player $x$ would do better by moving
more weight to its second preference. Therefore, the convex combination of $w$ and $w'$ is not an equilibrium.
\end{proof}